#include <stdio.h>
#define  DIMENSION 9
static int validate_row(char sudoku[DIMENSION][DIMENSION], int row)
{
	int i, bitmap = 0, n = 0;
	for (i = 0; i < DIMENSION; i++) {
		if (sudoku[row][i]){
			if (bitmap & (1 << sudoku[row][i]))
				return -1;
			else 
				bitmap |= (1 << sudoku[row][i]);
		}
	}
	return 0;	
}

static int validate_col(char sudoku[DIMENSION][DIMENSION], int col)
{
	int i, bitmap = 0, n = 0;
	for (i = 0; i < DIMENSION; i++) {
		if (sudoku[i][col]){
			if (bitmap & (1 << sudoku[i][col]))
				return -1;
			else 
				bitmap |= (1 << sudoku[i][col]);
		}
	}
	return 0;	
}

static int validate_square(char sudoku[DIMENSION][DIMENSION], int row, int col)
{
	int i, j, bitmap = 0, n = 0;
	for (i = row; i < row + 3; i++) {
		for (j = col; j < col + 3; j++) {
			if (sudoku[i][j]){
				if (bitmap & (1 << sudoku[i][j]))
					return -1;
				else 
					bitmap |= (1 << sudoku[i][j]);
			}
		}
	}
	return 0;	
}

static int validate_sudoku(char sudoku[DIMENSION][DIMENSION], int row, int col)
{
	if (validate_row(sudoku, row) == -1)
		return 0;
	if (validate_col(sudoku, col) == -1)
		return 0;
	if (validate_square(sudoku, (row/3)*3, (col/3)*3) == -1)
		return 0;
	return 1;
}
static void print_sudoku(char sudoku[][DIMENSION])
{
	int i, j;
	for (i = 0; i < DIMENSION; i++) {
		for (j = 0; j < DIMENSION; j++) {
			printf("%d ", sudoku[i][j]);
		}
		printf("\n");
	}
	printf("\n");
}
static int visit(char sudoku[][DIMENSION], int row, int col)
{
	if (sudoku[row][col]) {
		if (row == DIMENSION-1 && col == DIMENSION-1){
			return 0;
		} else {
			if (col < DIMENSION-1) {
				if (visit(sudoku, row, col+1) == 0) {
					return 0;
				} 
			} else {
				if (visit(sudoku, row+1, 0) == 0){
					return 0;
				}
			}
		}
	} else {
		int i;
		for (i = 1; i <= DIMENSION; i++) {
			sudoku[row][col] = i;
			if (validate_sudoku(sudoku, row, col)){
				if (visit(sudoku, row, col) == 0){
					return 0;
				}
			}
		}
		sudoku[row][col] = 0;
	}
	return -1;
}

void main(void)
{
	int i;
	char sudoku[DIMENSION][DIMENSION] = {
		{0, 0, 0, 0, 0, 2, 1, 0, 7},
		{0, 0, 2, 0, 0, 0, 6, 5, 0},
		{7, 0, 8, 9, 0, 5, 0, 0, 0},
		{0, 0, 0, 0, 9, 0, 0, 0, 0},
		{8, 0, 0, 0, 0, 7, 0, 0, 0},
		{0, 0, 3, 0, 0, 0, 2, 0, 0},
		{0, 0, 0, 6, 3, 1, 0, 0, 0},
		{0, 0, 5, 0, 2, 8, 0, 0, 3},
		{1, 0, 0, 7, 0, 0, 0, 0, 2}, 
	};
	print_sudoku (sudoku);
	if(visit(sudoku, 0, 0) == 0)
		print_sudoku (sudoku);
	else
		printf("there is not solution exsit for this puzzle.\n");
}
